package euler.p051_100;

import euler.MainEuler;

public class Euler069 extends MainEuler {
    /*
        Euler's Totient function, φ(n) [sometimes called the phi function],
        is used to determine the number of numbers less than n which are
        relatively prime to n.
        For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and
        relatively prime to nine, φ(9)=6.
        n   Relatively Prime    φ(n)    n/φ(n)
        2   1                     1       2
        3   1,2                   2       1.5
        4   1,3                   2       2
        5   1,2,3,4               4       1.25
        6   1,5                   2       3
        7   1,2,3,4,5,6           6       1.1666...
        8   1,3,5,7               4       2
        9   1,2,4,5,7,8           6       1.5
        10  1,3,7,9               4       2.5

        It can be seen that n=6 produces a maximum n/φ(n) for n ≤ 10.

        Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.
     */

    public String resolve() {

        int limite = 1000000;
        float maxDiv = 0;
        int maxN = 0;

        for (int i = 2; i <= limite; i++) {
            float div = ((float)i)/naturalHelper.phi(i);
            if (div > maxDiv) {
                maxDiv = div;
                maxN = i;
            }
        }

        return String.valueOf(maxN);
    }

}
